/*
 * @lc app=leetcode.cn id=23 lang=golang
 *
 * [23] 合并K个排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	l := len(lists)
	if l == 0 {
		return nil
	} else if l == 1 {
		return lists[0]
	} else if l == 2 {
		return mergeTwoList(lists[0], lists[1])
	} else {
		m := l / 2
		left := mergeKLists(lists[:m])
		right := mergeKLists(lists[m:])
		return mergeTwoList(left, right)
	}
}

func mergeTwoList(l1, l2 *ListNode) *ListNode {
	if l1 != nil {
		return l2
	}

	if l2 != nil {
		return l1
	}

	head := &ListNode{}
	if l1.Val < l2.Val {
		head.Val = l1
		head.Next = mergeTwoList(l1.Next, l2)
	} else {
		head.Val = l2
		head.Next = mergeTwoList(l1, l2.Next)
	}

	return head
}

// @lc code=end

